\documentclass[12pt, letterpaper]{article}

\usepackage{subfigure}
\usepackage{url}
\usepackage{pslatex}
\usepackage{amsmath}
\usepackage{commath}
\usepackage{graphicx}
\usepackage{caption}
\usepackage{multirow}
\usepackage{enumerate}
\usepackage[left=1.5in,  top=1.5in,  bottom=1in,  right=1in]{geometry}

\begin{document}
\title{Project Phase 0 Report}
\author{Xiao Yu (902641982) \\
        \texttt{xyu40@gatech.edu} 
        \and Xin Zhang (902763408) \\
        \texttt{xin.zhang@gatech.edu} 
        \and Cong Hou (902532366) \\
        \texttt{hou_cong@gatech.edu} 
        }
\maketitle

\section{Improvement}
\subsection{E-SSA form}
We improve the ssa form from the following two aspects in terms of phase 1.

\begin{itemize}

\item We hoist the $\pi$ node to the incoming edge and add new $\pi$ blocks.
When we try to insert a $\pi$ in the successor of a branch, if the successor
has multiple predecessors, we cannot insert that $\pi$ node into the successor
directly. Previously we just ignored that case and did not insert a $\pi$ node
for simplicity. In this version we deal with that case by insert a $\pi$ block
before the successor and insert a $\phi$ node in the successor to propagate the
information. The information of the $\phi$ node is recursively propagated as
the previous version.

\item We deal with the \texttt{switch} instructions in the current version.
Previously we only considered the branches resulting from compare instructions.
In the current version, we insert $\pi$ nodes for each \texttt{switch}
condition and propagate that information.

\end{itemize}
\subsection{More Cases Catched}
We catch two more cases than the paper describes:
\begin{enumerate}
\item Instructions like x = i + j, where i and j are both variables. The paper only considers the case where a variable adds a constant. For this case, if we want to compare if x is not greater than a.lenght+c, we need to compute the max values of i and j in the inequlity graph and compare max(i)+max(j) with a.length + c. In the max function, we traverse the inequality graph to find a value's possible maximum value. This function is similar to the prove function in the paper, and we treat the phi node (not pi node) as a max node and if a search starts from there we calculate the maximum returned value for all its arguments. We also check if a cycle is formed during the search.
\item Instructions like x = b*i, where b is a constant and i is a variable. If we want to compare x with a.length+c, in addition to propagating the comparation to its connected nodes as normal node in the graph, we would also compare i with a.length/b + c/b, and join the result. It would look like:
$$prove(a.length,x,c) = prove(a.length/b,y, c/w)\cup \bigcup prove(a.length,y,c-w)$$
y is the src node of every incoming edge of x.
\end{enumerate}

\section{Experiment Result and Discussion}

Table~\ref{tab:elim} shows our improvement over the previous version in terms
of the boundary check eliminated. Generally speaking, our current version
eliminates more checks than the previous one.  Table~\ref{tab:rt} shows the
execution time of the current version. We fixed a bug from previous version of
arrays that declare size zero.

\begin{table*}[!h]
\label{tab:elim}
\begin{center}
\begin{tabular}{|c|c|p{3cm}|p{3cm}|p{3cm}|}
\hline
Benchmark & Input & array bounds check added after -abc & previous & current\\
\hline
cjpeg.linked & testimg.ppm & 987 & 707 & 768\\
\hline
cjpeg.llvm & testimg.ppm & 490 & 304 & 391\\
\hline
encode.linked& clinton.pcm &78 &54 & 69\\
\hline
encode.llvm&clinton.pcm &83 &6 &80\\
\hline
mpeg2.linked & meil6v2.m2v & 467(431) & 341 &467\\
\hline
mpeg2.llvm & meil6v2.m2v & 396(360) & 287 &267\\
\hline
rawcaudio.linked & clinton.pcm & 6 & 0 & 3\\
\hline
rawcaudio.llvm & clinton.pcm &  3 & 0 & 0\\
\hline
rawdaudio.linked & clinton.pcm & 6 & 0 & 3\\
\hline
rawdaudio.llvm & clinton.pcm & 3 & 0 & 1\\
\hline
toast.linked & clinton.pcm & 525 & 509 & 510\\
\hline
toast.llvm & clinton.pcm & 350 &305 & 319\\
\hline
\end{tabular}
\end{center}
\caption{Redundant Array Bound Check Eliminated}
\label{tab:abc}
\end{table*}

\begin{table*}[!h]
\label{tab:rt}
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
Benchmark & Run Time(s) & Rum Time After -abc & Run Time After -gvn &Run Time -gvn -abcd  \\
\hline
cjpeg.linked & 1.754 & 1.717 & 1.397 & 1.350 \\
\hline
cjpeg.llvm & 2.511 & 3.579 & 2.827 & 2.054 \\
\hline
encode.linked& 0.437 & 0.522 &0.332 &0.305 \\
\hline
encode.llvm & 0.276 & 0.434 & 0.297 & 0.277 \\
\hline
mpeg2.linked & 0.854 & 1.458 & 1.069 & 1.114 \\
\hline
mpeg2.llvm & 1.559 & 0.278,f & 0.122,f & 0.126,f \\
\hline
rawcaudio.linked &0.053&  0.045 &0.046 & 0.044\\
\hline
rawcaudio.llvm & 0.038 & 0.043 & 0.042 & 0.042\\
\hline
rawdaudio.linked &0.049&  0.054 &0.045 & 0.044\\
\hline
rawdaudio.llvm & 0.036 & 0.042 & 0.041 & 0.041\\
\hline
toast.linked & 0.843 & 1.621 & 0.828 & 0.786\\
\hline
toast.llvm & 1.066 & 2.94 & 1.355 & 1.176 \\
\hline
\end{tabular}
\end{center}
\caption{Run Time(s) of the Transformed Program. *,f is the run time when program fails at a bound check}
\label{tab:performance}
\end{table*}


\begin{thebibliography}{9}

\end{thebibliography}

\end{document}

